#!/usr/bin/env python
#-*- coding:utf-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2019年05月23日
描    述：
Copyright (C) 2019 All rights reserved.
'''

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):
    def __init__(self):
        self.dict = {};

    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0;

        val = self.dict.get(root)
        if val != None:
            return val;

        maxleft = 0; maxright = 0
        maxleft = self.rob(root.left)
        maxright = self.rob(root.right)
            
        maxlleft = 0; maxrright = 0
        maxres = 0

        if root.left:
            maxlleft = self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            maxrright = self.rob(root.right.left) + self.rob(root.right.right)

        maxres = max(maxres, maxleft+maxright)
        maxres = max(maxres, maxlleft + maxrright + root.val)

        self.dict[root] = maxres
        return maxres

